﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;


namespace GenericLibrary.Common {

    public class JaggedArray<T> {

        class Section {

            private T[] _items;
            private int _nonDefaultCount;

            private Section() { }

            public Section(JaggedArray<T> array) {
                this._items = new T[array._sectionLength];
                this._nonDefaultCount = 0;
            }

            public T this[int index] {
                get {
                    return this._items[index];
                }
                set {
                    bool isOldDefault = object.Equals(this._items[index], default(T)), isNewDefault = object.Equals(value, default(T));
                    if(isOldDefault && !isNewDefault) {
                        this._nonDefaultCount++;
                    } else if(!isOldDefault && isNewDefault) {
                        this._nonDefaultCount--;
                    }
                    this._items[index] = value;
                }
            }

            public bool AllDefault {
                get { return this._nonDefaultCount == 0; }
            }

        }

        private int _length, _sectionLength;
        private Section[] _sections;

        private JaggedArray() { }

        public JaggedArray(int rows, int columns) {
            this._sections = new JaggedArray<T>.Section[rows];
            this._sectionLength = columns;
            this._length = rows * columns;
        }

        public int Rows {
            get {
                return this._sections.Length;
            }
        }

        public int Columns {
            get {
                return this._sectionLength;
            }
        }

        public int Length {
            get {
                return this._length;
            }
        }

        private int _debug_Section_new_Count = 0, _debug_Section_null_Count = 0;

        public T this[int row, int column] {
            get {
                if(this._sections[row] == null) {
                    return default(T);
                }
                return this._sections[row][column];
            }
            set {
                if(object.Equals(value, default(T)) && this._sections[row] == null) {
                    return;
                } else if(this._sections[row] == null) {
                    this._sections[row] = new JaggedArray<T>.Section(this);
                    Debug.Print("Section new:{0}, Section null:{1}", ++this._debug_Section_new_Count, this._debug_Section_null_Count);
                }

                this._sections[row][column] = value;

                if(this._sections[row].AllDefault) {
                    this._sections[row] = null;
                    Debug.Print("Section new:{0}, Section null:{1}", this._debug_Section_new_Count, ++this._debug_Section_null_Count);
                }
            }
        }


    }

    public class CompactArray<T> : IList<T> {

        private JaggedArray<T> _array0;
        private T[] _array1;

        private CompactArray() { }

        public CompactArray(int length, int sectionLength) {
            if(sectionLength > 0 && length / sectionLength >= 1) {
                this._array0 = new JaggedArray<T>(length / sectionLength, sectionLength);
                this._array1 = new T[length % sectionLength];
            } else {
                throw new Exception();
            }
        }

        private IEnumerable<T> Enumerate() {
            for(int i = 0, count = this.Count; i < count; i++) {
                yield return this[i];
            }
        }

        #region IList<T> Members

        public T this[int index] {
            get {
                if(index < this._array0.Length) {
                    return this._array0[index / this._array0.Columns, index % this._array0.Columns];
                } else {
                    return this._array1[index - this._array0.Length];
                }
            }
            set {
                if(index < this._array0.Length) {
                    this._array0[index / this._array0.Columns, index % this._array0.Columns] = value;
                } else {
                    this._array1[index - this._array0.Length] = value;
                }
            }
        }

        public int IndexOf(T item) {
            for(int i = 0; i < this.Count; i++) {
                if(item.Equals(this[i])) {
                    return i;
                }
            }
            return -1;
        }

        public void Insert(int index, T item) {
            throw new NotImplementedException();
        }

        public void RemoveAt(int index) {
            throw new NotImplementedException();
        }

        #endregion

        #region ICollection<T> Members

        public void Add(T item) {
            throw new NotImplementedException();
        }

        public void Clear() {
            throw new NotImplementedException();
        }

        public bool Contains(T item) {
            foreach(T t in this.Enumerate()) {
                if(item.Equals(t)) {
                    return true;
                }
            }
            return false;
        }

        public void CopyTo(T[] array, int arrayIndex) {
            foreach(T t in this.Enumerate()) {
                array[arrayIndex] = t;
                arrayIndex++;
            }
        }

        public int Count {
            get { return this._array0.Length + this._array1.Length; }
        }

        public bool IsReadOnly {
            get { return false; }
        }

        public bool Remove(T item) {
            throw new NotImplementedException();
        }

        #endregion

        #region IEnumerable<T> Members

        public IEnumerator<T> GetEnumerator() {
            return this.Enumerate().GetEnumerator();
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
            return this.Enumerate().GetEnumerator();
        }

        #endregion
    }

    //public class JaggedArray<T> : ICloneable {
    //    private int _columns;
    //    private T[][] _rows;
    //    private int[] _countNonDefaultByRow;

    //    private JaggedArray() { }

    //    public JaggedArray(int rows, int columns) {
    //        this._rows = new T[rows][];
    //        this._countNonDefaultByRow = new int[rows];
    //        this._columns = columns;
    //    }

    //    public int Rows {
    //        get {
    //            return this._rows.Length;
    //        }
    //    }

    //    public int Columns {
    //        get {
    //            return this._columns;
    //        }
    //    }

    //    public T this[int row, int column] {
    //        get {
    //            if(this._rows[row] == null) {
    //                return default(T);
    //            } else {
    //                return this._rows[row][column];
    //            }
    //        }
    //        set {
    //            if(!object.Equals(value, default(T))) {
    //                if(this._rows[row] == null) {
    //                    this._rows[row] = new T[this._columns];
    //                }
    //                if(object.Equals(this._rows[row][column], default(T))) {
    //                    this._countNonDefaultByRow[row]++;
    //                }
    //            } else if(this._rows[row] != null) {
    //                if(!object.Equals(this._rows[row][column], default(T))) {
    //                    this._countNonDefaultByRow[row]--;
    //                }
    //            }

    //            if(this._countNonDefaultByRow[row] == 0) {
    //                this._rows[row] = null;
    //            } else {
    //                this._rows[row][column] = value;
    //            }
    //        }
    //    }





    //    #region ICloneable Members

    //    public object Clone() {
    //        JaggedArray<T> clone = new JaggedArray<T>();
    //        clone._columns = this._columns;
    //        clone._countNonDefaultByRow = this._countNonDefaultByRow.Clone() as int[];
    //        clone._rows = this._rows.Clone() as T[][];
    //        return clone;
    //    }

    //    #endregion
    //}

    //public class BitArray : ICloneable
    //{
    //    private static byte[] _byteMask = new byte[] { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
    //    private byte[] _bytes;
    //    private int[] _dimensions, _coefficients;

    //    private BitArray() { }

    //    public BitArray(params int[] dimensions)
    //    {
    //        if (dimensions.Length == 0)
    //        {
    //            throw new Exception();
    //        }

    //        foreach (int i in dimensions)
    //        {
    //            if (i <= 0)
    //            {
    //                throw new Exception();
    //            }
    //        }

    //        this._dimensions = dimensions;

    //        this._coefficients = new int[this._dimensions.Length];
    //        this._coefficients[0] = 1;
    //        for (int i = 1; i < this._coefficients.Length; i++)
    //        {
    //            this._coefficients[i] = this._coefficients[i - 1] * this._dimensions[i - 1];
    //        }

    //        int bitCount = 1;
    //        foreach (int dim in this._dimensions)
    //        {
    //            bitCount *= dim;
    //        }

    //        this._bytes = new byte[(int)Math.Ceiling(bitCount / 8d)];
    //    }

    //    public int Rank
    //    {
    //        get
    //        {
    //            return this._dimensions.Length;
    //        }
    //    }

    //    public int GetDimension(int ordinal)
    //    {
    //        return this._dimensions[ordinal];
    //    }

    //    private int GetBitIndex(int[] index)
    //    {
    //        int bitIndex = 0;
    //        for (int i = 0; i < this._coefficients.Length; i++)
    //        {
    //            bitIndex += this._coefficients[i] * index[i];
    //        }
    //        return bitIndex;
    //    }

    //    public bool this[params int[] index]
    //    {
    //        get
    //        {
    //            int bitIndex = this.GetBitIndex(index);
    //            return Convert.ToBoolean(this._bytes[bitIndex / 8] & _byteMask[bitIndex % 8]);
    //        }
    //        set
    //        {
    //            int bitIndex = this.GetBitIndex(index);
    //            int byteIndex = bitIndex / 8;

    //            if (value)
    //            {
    //                this._bytes[byteIndex] = Convert.ToByte(this._bytes[byteIndex] | _byteMask[bitIndex % 8]);
    //            }
    //            else
    //            {
    //                this._bytes[byteIndex] = Convert.ToByte(this._bytes[byteIndex] & (~_byteMask[bitIndex % 8]));
    //            }
    //        }
    //    }

    //    #region ICloneable Members

    //    object ICloneable.Clone()
    //    {
    //        BitArray clone = new BitArray();
    //        clone._dimensions = this._dimensions.Clone() as int[];
    //        clone._coefficients = this._coefficients.Clone() as int[];
    //        clone._bytes = this._bytes.Clone() as byte[];
    //        return clone;
    //    }

    //    #endregion
    //}

    //public class BitArray {
    //    private static byte[] _bitMask = new byte[] { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
    //    private IList<byte> _bytes;
    //    private int[] _dimensions, _coefficients;

    //    private BitArray() { }

    //    public BitArray(params int[] dimensions) {
    //        if(dimensions.Length == 0) {
    //            throw new Exception();
    //        }

    //        foreach(int i in dimensions) {
    //            if(i <= 0) {
    //                throw new Exception();
    //            }
    //        }

    //        this._dimensions = dimensions;

    //        this._coefficients = new int[this._dimensions.Length];
    //        this._coefficients[0] = 1;
    //        for(int i = 1; i < this._coefficients.Length; i++) {
    //            this._coefficients[i] = this._coefficients[i - 1] * this._dimensions[i - 1];
    //        }

    //        int bitCount = 1;
    //        foreach(int dim in this._dimensions) {
    //            bitCount *= dim;
    //        }

    //        int byteCount = (int) Math.Ceiling(bitCount / 8d);
    //        if(byteCount <= 1024) {
    //            this._bytes = new List<byte>(byteCount);
    //        } else {
    //            this._bytes = new CompactArray<byte>(byteCount, 1024);
    //        }

    //    }

    //    public int Rank {
    //        get {
    //            return this._dimensions.Length;
    //        }
    //    }

    //    public int GetDimension(int ordinal) {
    //        return this._dimensions[ordinal];
    //    }

    //    private int GetBitIndex(int[] index) {
    //        int bitIndex = 0;
    //        for(int i = 0; i < this._coefficients.Length; i++) {
    //            bitIndex += this._coefficients[i] * index[i];
    //        }
    //        return bitIndex;
    //    }

    //    public bool this[params int[] index] {
    //        get {
    //            int bitIndex = this.GetBitIndex(index);
    //            int byteIndex = bitIndex / 8;
    //            return Convert.ToBoolean(this._bytes[byteIndex / this._bytes.Columns, byteIndex % this._bytes.Columns] & _bitMask[bitIndex % 8]);
    //        }
    //        set {
    //            int bitIndex = this.GetBitIndex(index);
    //            int byteIndex = bitIndex / 8;
    //            int row = byteIndex / this._bytes.Columns, column = byteIndex % this._bytes.Columns;

    //            if(value) {
    //                this._bytes[row, column] = Convert.ToByte(this._bytes[row, column] | _bitMask[bitIndex % 8]);
    //            } else {
    //                this._bytes[row, column] = Convert.ToByte(this._bytes[row, column] & (~_bitMask[bitIndex % 8]));
    //            }
    //        }
    //    }


    //}

    public class BitArray {
        private static byte[] _bitMask = new byte[] { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
        private IList<byte> _bytes;
        private int[] _dimensions, _coefficients;

        private BitArray() { }

        public BitArray(params int[] dimensions) {
            if(dimensions.Length == 0) {
                throw new Exception();
            }

            foreach(int i in dimensions) {
                if(i <= 0) {
                    throw new Exception();
                }
            }

            this._dimensions = dimensions;

            this._coefficients = new int[this._dimensions.Length];
            this._coefficients[0] = 1;
            for(int i = 1; i < this._coefficients.Length; i++) {
                this._coefficients[i] = this._coefficients[i - 1] * this._dimensions[i - 1];
            }

            int bitCount = 1;
            foreach(int dim in this._dimensions) {
                bitCount *= dim;
            }

            //int byteCount = (int) Math.Ceiling(bitCount / 8d);
            //if(byteCount <= 1024) {
            //    this._bytes = new byte[byteCount];
            //} else {
            //    this._bytes = new CompactArray<byte>(byteCount, 1024);
            //}

            this._bytes = new byte[(int) Math.Ceiling(bitCount / 8d)];
        }

        public int Rank {
            get {
                return this._dimensions.Length;
            }
        }

        public int GetDimension(int ordinal) {
            return this._dimensions[ordinal];
        }

        private int GetBitIndex(int[] index) {
            int bitIndex = 0;
            for(int i = 0; i < this._coefficients.Length; i++) {
                bitIndex += this._coefficients[i] * index[i];
            }
            return bitIndex;
        }

        public bool this[params int[] index] {
            get {
                int bitIndex = this.GetBitIndex(index);
                return Convert.ToBoolean(this._bytes[bitIndex / 8] & _bitMask[bitIndex % 8]);
            }
            set {
                int bitIndex = this.GetBitIndex(index);
                int byteIndex = bitIndex / 8;

                if(value) {
                    this._bytes[byteIndex] = Convert.ToByte(this._bytes[byteIndex] | _bitMask[bitIndex % 8]);
                } else {
                    this._bytes[byteIndex] = Convert.ToByte(this._bytes[byteIndex] & (~_bitMask[bitIndex % 8]));
                }
            }
        }


    }
}
